NetNews Offline 2/NetNews Offline Volume 2.iso/news/comp/sys/amiga/programmer/7247

Internet Message Format | 1996-08-05 | 7.0 KB

Path: news.NetVision.net.il!news
From: Jack <[e-mail]>
Newsgroups: comp.sys.amiga.programmer
Subject: Re: 680X0 -> PPC translator?
Date: Fri, 12 Apr 1996 17:53:36 -0700
Organization: NetVision LTD.
Message-ID: <[e-mail]>
References: <[e-mail]> <[e-mail]><[e-mail]>
        <[e-mail]><[e-mail]>
        <[e-mail]><[e-mail]>
        <[e-mail]> <[e-mail]> <[e-mail]> <[e-mail]>
NNTP-Posting-Host: ts004p6.pop4a.netvision.net.il
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
X-Mailer: Mozilla 2.01 (Win16; I)

Mans Engman wrote:
>
> >Mans Engman wrote:
> >>
> >> Once you think a bit, it's easy to show (prove!) that static code<->data
> >> distinction can't be determined by an algorithm. It is what theorists call
> >> an "undecidable" problem. Granted, for a "real" computer with a finite
> >> amount of memory/indata it can be "solved" by brute-force search, but this
> >> is not a practical approach.
>
> >many problems aren't solvable with today's technology, but it doesn't mean
> >they're not solvable with other yet-to-devised methods, now do they??
>
> What do you mean? You think someone will come up with algorithms to solve
> problems *beyond* what a Turing machine can?
> excuse my poor knowledge of the english language, but i don't know what the hell turing
machines are, so i can't reply to that.

> >>
> >> Okay, let's go on:
> >>
> >> 1) Hilberts 10th problem is a well known, proven undecidable problem. The
> >> problem is determining whether an integer polynomial equation has a
> >> (integer) solution.
>
> >oh please, stick to the subject at hand and stop making irrelevant analogies.
>
> This isn't an "irrelevant analogy", it's a simple example (among *many*
> undecidable problems) used to construct a program for which you can't analyse
> the program flow statically.

'among many', PRECISLEY my point, your point still doesn't make it clear why static
code translation isn't possible, don't generalise on questionable theories and be mucho more
concrete, PLEASE!!!!

>
> >> 2) Now imagine a program calculating some function on the indata x, y, ...
> >> and uses the result as a pc-relative address where we jump. This function,
> >> and the rest of the program can be constructed such that for all x, y, ...
> >> we jump to a legal piece of code. Between these code chunks we will of
> >> course put data to confuse anyone analysing the program! :)
>
> >you havn't really thought about the implementation of your hypothetic
> >scenario have you?! in order for what you said to work you must store the
> >offsets from the current locations in some array, and the inputs are used to
> >calculate the array entry that should be selected that's all.
>
> No, I didn't intend using an array.
> I can easily construct a function that will be within certain bounds,
> and will always be a multiple of, say, 42, and you'll not be able to
> know/prove that by using an algorithm. That's the whole point of the example;
> the function itself is very easy to calculate, but it is undecidable what the
> possible results will be.

No,no,no that's not what you said, you refered to making a pc-relative jump using some
calculated value returned by some mathemtic function which is simply not possible
cus then you'd have to call the function from distances of integer multiples of
your defined interval (say 42) otherwise you can't call the function from any other place that way and
that's simply not practical to use in any program, AH AH no sirry.
and even if you use this method there's no problem detecting the function which calculates
this offset and figure which intervals are being used in the calculation. after all the interval
is fixed and the interface of fata exchange between the caller and the callee is known
to the analysing program, so it could discern the pattern and actually jump in integer multiples
of that interval to either of the 2 directions (up,down) and find the called functions that way.


>
> Even if you use an array, you'd have exactly the same problem trying to know
> which elements of the array are used as code pointers, and which of them are
> something completely different. Like pointers to data which looks like
> code, but isn't used as such (see below).
> not if the pointed code bytes make some sense ie use defined data addresses, make valid calls,
has an RTS at the end, no, it's just too ordered for it to be just random chaos, now would it.

> >calculating the
> >correct number of bytes to skip from arbitrary inputs without using this
> >method is next to impossible and most practical applications don't use this
> >method.
>
> It's perhaps not practical to have this very-advanced-function(tm) to
> calculate jump-addresses, but it's legal and possible.

your 'highly' advanced feature will just have to wait for version 2.0 of the translator,
i guess, initial target is for 'less-advanced' programs if you wish to call it that way
which consist of ALL existing programs.


>
> >you can't confuse the analysing program because ALL code sequences
> >can be identified without a problem, every sequence of words that makes sense
> >as a code sequence must be executable code and therefore can be identified.
> >by 'makes sense' i mean that the code makes references to other parts of the
> >program and a sequence of code instructions is  maintained, you simply have
> >to follow the logic of that section and see if it's interrupted by some data
> >word without a jump that would prevent such a thing from happening.
>
> What you or your analyser thinks "makes sense" as executable code is not
> neccessarily code that will be executed.
>
> For instance, if some
> section of my program is
>
> $7070
> $c1c1
> $4e75
>
> and I some of the words as data (nice bit masks), you have
> no right to interpret the sequence as
>
> moveq   #112,d0
> muls    d1,d0
> rts
>
> even though that would "make sense" as legal code.
>yes, true, but you can defer the translation until you ,ake sure someone's calling
this piece of code, which can be done by further analysing the rest of the program.
and besides, if a sequence of words makes some sense ie makes valid references to other
memory areas and it's a long section then it's probably code, even you would have to agree
that this is highly unlikely that it's some other data.

> The best thing you can do about this is to have the both the original data
> and the translated part, in the final translated program.
> Then, you could determine, at *run-time*, how it is used.
>


NO!! no way, all the required information is in the binary itself, no need for any run-time
analysis, you just need to know how to correctly distill this information into a useful one
which i have described how in previous articles. give me problems i can't solve and then
i'll raise my white flag otherwise, it's on with the crusade and the pirate skull flag
is still held up high. hehehe


Avi Lev.